package sort;

/**
 * 计数排序
 *
 */
public class CountSort implements ISort{

	public void sort(int[] arr) {
		int maxMin[] = getMaxMin(arr);
		int max = maxMin[0];
		int min = maxMin[1];
		int delta = max - min + 1;
		int[] tmpArr = new int[delta];
		for (int i = 0; i < arr.length; i++) {
			tmpArr[arr[i] - min]++;
		}
		int idx = 0;
		for (int i = 0; i < delta; i++) {
			for (int j = 0; j < tmpArr[i]; j++) {
				arr[idx++] = min + i;
			}
		}
	}

	private int[] getMaxMin(int[] arr) {
		int min = arr[0];
		int max = arr[0];
		for (int i = 0; i < arr.length; i++) {
			if (min > arr[i]) {
				min = arr[i];
			}
			if (max < arr[i]) {
				max = arr[i];
			}
		}
		return new int[] { max, min };
	}

	public static void main(String[] args) {
		int arr[] = { 95, 94, 91, 98, 99, 90, 99, 93, 91, 92 };
		CountSort countSort = new CountSort();
		countSort.sort(arr);
		ISort.printArr(arr);
	}

}
